package com.wenhao.leetcode.medium;

/**
 * 题目：https://leetcode-cn.com/problems/unique-binary-search-trees/
 * 不同的二叉搜索树
 * @author Wenhao Tong
 * @date 2021/7/12 下午10:50
 */
public class LeetCode96 {
    public static void main(String[] args) {
        LeetCode96 leetCode96 = new LeetCode96();
        int i = leetCode96.numTrees(2);
        System.out.println(i);
    }
    int[] result;
    public int numTrees(int n) {
        result = new int[n + 1];
        result[0] = 1;
        return solution(n);
    }
    private int solution(int n) {
        if (result[n] != 0) return result[n];
        for (int i = 0;i < n;i++) {
            result[n] += solution(i) * solution(n - i - 1);
        }
        return result[n];
    }
}
